#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	// memory buffer: defined in BTreeNode.h
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{  return pf.write(pid, buffer); }

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{  return 0; }

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{  
	//size of the buffer is PageFile::PAGE_SIZE]
	int size_of_key = sizeof(int);
	int size_of_RecordId = sizeof(RecordId); 

	// offset of the first key
	int *k = &buffer[0];
	int search = 1;
	// for comparsion
	int temp1;
	int temp2;

	
    if(getKeyCount() >= 85) {
        cout << "Leaf node full" << endl;
        return RC_NODE_FULL;
    }

	// search until we insert the pair or cannot find a place 
	while(search > 0)
	{
		// get the key we want to compare
		memcpy(&temp1, k, size_of_key);

		// get the offset of the next pair  
		k = k + size_of_key + size_of_RecordID;
		memcpy(&temp2, k, size_of_key);

		// inset if key > temp and there is a space in the next field
		if ((key > temp1) && (temp2 == 0) ) //assume the value is negative if it is empty
		{
			memcpy(&buffer[k], &rid, size_of_RecordId);
			memcpy(&buffer[k] + size_of_RecordId, &key, size_of_key);
			search = 0; // stop searching
		}
	
		// stop if out of range
		if ((k + size_of_key + size_of_RecordID) > 1024)
			search = 0;
	}

	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	int size_of_key = sizeof(int);
	int size_of_RecordId = sizeof(RecordId); 

	// second half of the node
	int *offset = (geyKeyCount()/2) * (size_of_key + size_of_RecordId); 
	
	int copy = 1;
	int temp_key;
	RecordId& temp_id;

	while(copy > 0)
	{
		memcpy(&temp_key, offset, size_of_key);
		memcpy(&temp_id, offset + size_of_RecprdID, size_of_RecprdId)l
		insert(temp_key,temp_id);
		offset = offset + size_of_key + size_of_RecordId
		if (offset > 1024)
			copy = 0;
	}
	//memset((geyKeyCount()/2) * (size_of_key + size_of_RecordId),0, ) length
	
	if (key > siblingkey)
		sibling.insert(key,rid);
	else
		insert(key,rid);
	return 0; 
}
/
/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int size_of_key = sizeof(int);
	int size_of_RecordId = sizeof(RecordId); 


	// offset of the buffer
	int *offset = &buffer;
	int entry_number = 0;
	int search = 1;
	int temp;
	while(search > 0)

	{
		// get the key we want to compare
		memcpy(&temp, offset, size_of_key);		

		if (temp >= searchkey)  
		{
			eid = entry_number;
			search = 1; // stop searching
		}
		// get the offset of the next pair  
		offset = offset + size_of_key + size_of_RecordID;
		entry_number++;

		// stop if out of range
		if ((offset + size_of_key + size_of_RecordID) > 1024)
			search = 1;
	}
	return 0; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	int entry = 0;
	int size_of_key = sizeof(int);
	int size_of_RecordId = sizeof(RecordId); 
	int *offset = &buffer[0];
	while(search > 0)
	{
		if (eid >= rid)
		{
			memcpy(&key, offset, size_of_key);
			memcpy(&rid, offset + size_of_key, size_of_RecordId);
			search = 0;
		}
		offet = offset + size_of_key + size_of_RecordId; 
		entry++;
	}
	
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageID pid;
	int size_of_ID = sizeof(PageId);
	int size_of_key = sizeof(int);
	int *offset = &buffer[0];

	// |key|pid|sid| the pid should be right after the key
	offset = offset + size_of_key;

	return (memcpy(&pid, offset, size_of_ID));
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	int *offset = &buffer[0] + sizeof(int);
	memcpy(offset, &piid, sizeof(PageId));

	return 0; }


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
    int retval = 0;
    //first four bytes stores number of records in a page
    memcpy(&retval, &buffer, sizeof(int));   
    return retval;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 

	int size_of_key = sizeof(int);
	int size_of_ID = sizeof(PageId);
	int size_of_RID = sizeof(RecordId);

	int slot_size = size_of_key + size_of_RID;
	int total_size = getKeyCount() * slot_size;

	
	if(total_size >= PageFile::PAGE_SIZE - slot_size) {
		cout << "Non-leaf node full" << endl;
		return RC_NODE_FULL;
	}
	
	//skip number of keys, skip first pid
	char* offset = &(buffer[0]) + size_of_key + size_of_ID;
	int i = 0;
	
	int currKey;
	while (offset) {

		memcpy(&currKey, offset, size_of_key);

		if(currKey == 0) {
			break;
		}
		if (currKey < key) {
			offset += slot_size;
			i++;
		} else {
			break;
		}
	}
	
	//set the new key count
	int currKeyCount = getKeyCount();
	currKeyCount++;
	offset = &(buffer[0]);
	memcpy(offset, &currKeyCount, size_of_key);
	
	return 0;
}

RC BTNonLeafNode::readEntry(int eid, int& key) {
	
	int size_of_key = sizeof(int);
	int size_of_ID = sizeof(PageId); 
	int slot_size = size_of_key + size_of_ID;

	char* offset = &(buffer[0]) + size_of_key;
	
	while(offset) {

		offset += size_of_ID;

		if(eid == 0) {

			memcpy(&key, offset, size_of_key);
			break;

		}
		offset += slot_size;
	}
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	//memcpy half the current node to the sibling node
	//get the first key of the sibling node, store it in the return param
	//call insert(key, rid) to put the new {key, rid} pair in the node

	int size_of_key = sizeof(int);
	int size_of_ID = sizeof(PageId); 
	int slot_size = size_of_key + size_of_ID;
	int total_size = getKeyCount() * slot_size;
	char* offset = &(buffer[0]) + size_of_key;
	
	int i = 0;
	while(i < (getKeyCount()/2)) {
		offset += slot_size;
		i++;
	}
	
	//increment once more to get past the last record
	char* temp = (char*) malloc(PageFile::PAGE_SIZE * size_of_key);
	char* head = temp;

	//save the last half of the data
	int curr_size = total_size - (slot_size * (getKeyCount() / 2));
	memset(temp, 0, 1024*sizeof(char));
	memcpy(temp, offset, curr_size);
	
	//remove old data from current node
	memset(offset, 0, curr_size);
	int newKey = getKeyCount() / 2;
	memcpy(buffer, &newKey, size_of_key);
	
	//extract ALL the data from the original node
	//insert them into the new node using the insert function
	while(temp) {
		int k;
		PageId p;
		memcpy(&k, temp, size_of_key);
		if(k == 0) {
			break;
		}
		temp += size_of_key;
		memcpy(&p, temp, size_of_ID);
		temp += size_of_ID;
		if(sibling.insert(k, p) != 0) {
			free(head);
			return RC_FILE_WRITE_FAILED;
		}
	}
	free(head);
	
	if(sibling.readEntry(0, midKey) != 0) {
		return RC_FILE_READ_FAILED;
	}
	
	//insert the new key that we're trying to insert
	if(key < midKey) {
		if(insert(key, pid) != 0){
			return RC_FILE_WRITE_FAILED;
		}
	} else {
		if(sibling.insert(key, pid) != 0) {
			return RC_FILE_WRITE_FAILED;
		}
	}
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int size_of_key = sizeof(int);
	int size_of_ID = sizeof(PageId); 
	int slot_size = size_of_key + size_of_ID;

	int curr_key;
	char *offset = &buffer[0] + size_of_key; //2*size_of_key??

	while(offset) 
	{
		memcpy(&curr_key, offset, size_of_key);
	
		if(curr_key != 0 && curr_key < searchKey) {

			offset += size_of_key;

		} else {

			offset -= size_of_ID;
			memcpy(&pid, offset, size_of_ID);
			break;

		}
		offset += slot_size;
	}
	return 0;	
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{

	char* offset = &(buffer[0]);
	int size_of_key = sizeof(int);
	int size_of_ID = sizeof(PageId);

	offset += size_of_key;
	memcpy(offset, &pid1, size_of_ID);

	offset += size_of_ID;
	memcpy(offset, &key, size_of_key);
	
	offset += size_of_key;
	memcpy(offset, &pid2, size_of_ID);
	
	int k = 1;
	memcpy(buffer, &k, size_of_key);
	
	return 0; 
}
